package cn.dapeng.array;

import cn.dapeng.utils.BuilderArray;

// 峰值元素是指其值严格大于左右相邻值的元素
// 给你一个整数数组 nums，已知任何两个相邻的值都不相等
// 找到峰值元素并返回其索引
// 数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
// 你可以假设 nums[-1] = nums[n] = 无穷小
// 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
public class BSFindPeakNum {

    // 测试链接 : https://leetcode.cn/problems/find-peak-element/
    public static int findPeakNum(int[] array) {

        if (array == null) {
            return -1;
        }
        if (array.length == 1) {
            return 0;
        }
        if (array[0] > array[1]) {
            return 0;
        }
        if (array[array.length - 1] > array[array.length - 2]) {
            return array.length - 1;
        }

        int l = 1, r = array.length - 2, ans = 0, m;

        while (l <= r) {
            m = l + ((r - l) >> 1);
            if (array[m] < array[m - 1]) {
                r = m - 1;
            } else if (array[m] < array[m + 1]) {
                l = m + 1;
            } else {
                ans = m;
                break;
            }
        }
        return ans;
    }

    public static boolean check(int[] array, int index) {
        if (array.length == 0) {
            return -1 == index;
        }
        int length = array.length;

        if (index == 0) {
            if (length == 1) {
                return true;
            }
            return array[0] > array[1];
        }

        if (length - 1 == index) {
            return array[index - 1] < array[index];
        }

        return array[index - 1] < array[index] && array[index] > array[index + 1];
    }

    public static void main(String[] args) {
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++) {
            int[] array = BuilderArray.builderNoRepeatArray(100, 10);
            int index = findPeakNum(array);
            if (!check(array, index)) {
                System.out.println("Oops");
                System.out.println(index);
                BuilderArray.print(array);
                break;
            }
        }
    }
}
